package com.leecode;

/**
 * 19. 删除链表的倒数第N个节点
 *
 * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
 *
 * 示例：
 *
 * 给定一个链表: 1->2->3->4->5, 和 n = 2.
 *
 * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
 */
public class Leet19 {
	public static void main(String[] args) {
		ListNode test5 = new ListNode(5);
		ListNode test4 = new ListNode(4);
		ListNode test3 = new ListNode(3);
		test4.next = test5;
		test3.next=test4;

		new Leet19().removeNthFromEnd(test3, 2);
	}

	int i;

	/**
	 * 考点:找出倒数第n节点,用该节点的next代替它自己
	 * 考点:recur返回listNode还是返数字??还是void???,只返回个head,内部随你搞,所以void
	 * 考点:recur,改变本层节点没有用,不传递"改变状态",也就是改变本层不影响外层
	 * 考点:改代码,改变本层->改变上层->bug:1节点删1倒1,2节点删倒2,所以需要一开始就要在head前面"构建一个dummy节点"
	 */
	public ListNode removeNthFromEnd(ListNode head, int n) {
		if(head==null)return null;

		ListNode dummy=new ListNode(-1);//构建的上层dummy成功了,100%,77%
		dummy.next=head;

		recur(dummy,n+1);
		return dummy.next;
	}

	int count=-1;
	public void recur(ListNode head,int n){
		if(head==null){
			count++;
			return;
		}

		recur(head.next,n);
		count++;
		if(count==n){
			head=head.next;//bug:对应n,又出现了"改变"不传递的现象
//			head.next=head.next.next;//对应n+1
			return;
		}
	}
}
